"""
NC73 数组中出现次数超过一半的数字
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=117&&tqId=37770&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param numbers int整型一维数组
# @return int整型
#

from typing import List
from collections import Counter


class Solution:

    def method1(self, nums: List[int]) -> int:
        """
        使用collections.Counter计数
        """
        if not nums:
            return

        size = len(nums)
        c = Counter(nums)
        v, times = c.most_common(1)[0]
        if times > size//2:
            return v
        
    def method2(self, nums: List[int]) -> int:
        # 输入描述：保证数组输入非空，且保证有解
        # 不用考虑特殊情况
        memo = {}
        size = len(nums)
        for v in nums:
            memo[v] = memo.get(v, 0) + 1

            if memo[v] > size//2:
                return v

    def MoreThanHalfNum_Solution(self, numbers: List[int]) -> int:
        # write code here
        # 输入描述：保证数组输入非空，且保证有解
        return self.method2(numbers)


def test():
    obj = Solution()
    nums = [1, 2, 3, 2, 2, 2, 5, 4, 2]
    res = obj.MoreThanHalfNum_Solution(nums)
    print(res)


if __name__ == "__main__":
    test()
